package arithmetic2.day01;

public class demo03 {
    public static void main(String[] args) {
        System.out.println(oddNum(new int[]{1, 1, 2, 2, 3}));
    }

    //数组中所有数都出现了偶数次，有一个数出现了奇数次，求这个出现奇数次的数
    public static int oddNum(int arr[]) {
        int eor = 0;
        for (int num : arr) {
            eor ^= num;
        }
        return eor;
    }

    //数组中所有数都出现了偶数次，有两个数出现了奇数次，求这两个出现奇数次的数
    public static int[] twoOddNum(int arr[]) {
        int res[] = new int[2];
        int eor = 0;
        for (int num : arr) {
            eor ^= num;
        }
        //此时的eor = a^b,因为a!=b，所以eor！=0，那么eor的二进表示中必定有一位是1
        //得到eor的最右边的1
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;
        //将数组中与rightOne中1不相同位置的数与onlyOne异或
        for (int num : arr) {
            if ((num & rightOne) == 0) {
                onlyOne ^= num;
            }
        }
        //此时onlyOne为所求的一个数
        res[0] = onlyOne;
        res[1] = eor^onlyOne;
        return res;
    }
}
